package com.dhnsoft.代码随想录.哈希表;

import java.util.*;

/**
 * ClassName: d07_15_三数之和
 * Package: com.dhnsoft.代码随想录.哈希表
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/15 11:27
 * @Version 1.0
 */
public class d07_15_三数之和 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,-1,-1,0};
        List<List<Integer>> lists = threeSum2(nums);
        System.out.println(lists);
    }

    public static List<List<Integer>> threeSum2(int[] nums) {
        //排序数组从小到大的顺序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i=0;i<nums.length;i++){


            //若nums[i]>0，由于数组已经排好序，则后面不可能有负数能相加为0，所以跳出循环
            if(nums[i]>0){
                return result;
            }
            //若当前i的值等于i-1的值证明是当前值重复，会生成一个重复的元组，所以跳过该循环
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            //定义一个left指向i的下一位
            int left = i+1;
            //定义一个right指向数组末尾
            int right = nums.length-1;
            //若left与right碰到则跳出循环
            while (left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
                else{
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //防止陷入到后续重复的值
                    while (right>left&&nums[right]==nums[right-1]){
                        right--;
                    }
                    while (right>left&&nums[left]==nums[left+1]){
                        left++;
                    }
                    right--;
                    left++;

                }

            }
        }
        return result;
    }


    public static List<List<Integer>> threeSum(int[] nums) {
        Map<Integer,Integer> map1 = new HashMap<>();
        Map<Integer,List<List<Integer>>> map2 = new HashMap<>();
        int k = 0;
        for (int i=0;i<nums.length;i++){
            for (int j=i+1;j<nums.length;j++){
                List<Integer> list = new ArrayList<>();
                List<Integer> list2 = new ArrayList<>();
                List<List<Integer>> all = new ArrayList<>();
                list.add(i);
                list.add(j);
                list2.add(nums[i]);
                list2.add(nums[j]);
                all.add(list);
                all.add(list2);
                if(map1.containsKey(nums[i]+nums[j])){
                    continue;
                }
                else{
                    map1.put(nums[i]+nums[j],k);
                    map2.put(k++,all);
                }
                map1.put(nums[i]+nums[j],k);
                map2.put(k++,all);
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        List<List<Integer>> keyResult = new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            Integer key = map1.get(0 - nums[i]);
            if(key!=null){
                List<List<Integer>> lists = map2.get(key);
                List<Integer> keys = lists.get(0);
                List<Integer> values = lists.get(1);
                if(!keys.contains(i)&&values.size()<3){
                    values.add(nums[i]);
                    keys.add(i);
                    result.add(values);
                    keyResult.add(keys);
                }
            }
        }
        Set<List<Integer>> resultSet = new HashSet<>(); // 使用Set来去重
        for (List<Integer> integers : result) {
            Collections.sort(integers);
        }
        for (List<Integer> integers : result) {
            resultSet.add(integers);
        }

        return new ArrayList<>(resultSet);

    }
}
